#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include "tree.h"

using namespace std;

vector<int> get_in_order_through_parent(Tree* root)
{
    Tree *pre = NULL, *cur = root;

    vector<int> ans;
    while(1) {
        if (cur->left && cur->left != pre) {
            pre = cur;
            cur = cur->left;
        } else if (cur->right && cur->right != pre) {
            pre = cur;
            ans.push_back(cur->data);
            cur = cur->right;
        } else {
            ans.push_back(cur->data);
            while(cur->parent && cur == cur->parent->right) {
                cur = cur->parent;
            }
            if (!cur->parent)
                break;
            pre = cur;
            cur = cur->parent;
        }
    }
    return ans;
}


vector<int> get_post_order_through_parent(Tree* root)
{
    Tree *pre = NULL, *cur = root;

    vector<int> ans;
    while(1) {
        if (cur->left && cur->left != pre) {
            pre = cur;
            cur = cur->left;
        } else if (cur->right && cur->right != pre) {
            pre = cur;
            cur = cur->right;
        } else {
            ans.push_back(cur->data);
            while(cur->parent && cur == cur->parent->right) {
                cur = cur->parent;
                ans.push_back(cur->data);
            }
            if (!cur->parent)
                break;
            pre = cur;
            cur = cur->parent;
        }
    }
    return ans;
}


vector<int> get_pre_order_through_parent(Tree* root)
{
    Tree *pre = NULL, *cur = root;

    vector<int> ans;
    while(1) {
        if (cur->left && cur->left != pre) {
            pre = cur;
            ans.push_back(cur->data);
            cur = cur->left;
        } else if (cur->right && cur->right != pre) {
            if (pre != cur->left) ans.push_back(cur->data);
            pre = cur;
            cur = cur->right;
        } else {
            if (pre != cur->left) ans.push_back(cur->data);
            while(cur->parent && cur == cur->parent->right) {
                cur = cur->parent;
            }
            if (!cur->parent)
                break;
            pre = cur;
            cur = cur->parent;
        }
    }
    return ans;
}


//hackie
vector<int> get_pre_order_through_parent2(Tree* root)
{
	vector<int> results;
	while (root!=0) {
		Tree* previous = 0;
		do {
			results.push_back(root->data);
			previous = root;
			root = root->left;
		} while (root!=0);
		// now root == 0 && previous is the Tree that doesn't have left child
		if (previous->right!=0) {
			// go down the right branch
			root = previous->right;
			continue;
		}
		// Now need to go above
		Tree* parent = previous->parent;
		while (parent && (parent->right == previous || parent->right==0)) {
			previous = parent;
			parent = previous->parent;
		}
		if (parent==0) { // done
			return results;
		}
		// parent->right is not empty
		root = parent->right;
	}
	return results;
}

vector<int> get_post_order_through_parent2(Tree* root)
{
	vector<int> results;
	while (root!=0) {
		Tree* previous; 
		do {
			previous = root;
			if (root->left) {
				root = root->left;
			} else {
				root = root->right;
			}
		} while (root); 
		// Now root==0 & previous has no kid 
		results.push_back(previous->data);
		// now need to go up
		Tree* parent = previous->parent;
		while (parent && (parent->right==0 || parent->right==previous)) {
			results.push_back(parent->data);
			previous = parent;
			parent = previous->parent;	
		}
		if (parent==0) {
			return results;
		}
		root = parent->right;
	}
	return results;
}

vector<int> get_in_order_through_parent2(Tree* root) 
{
	vector<int> results;
	while (root!=0) {
		while (root->left!=0) {
			root = root->left;
		}
		results.push_back(root->data);
		// now check if root->right is 0 or not, 
		// if not 0, go to root->right, otherwise go up
		if (root->right!=0) {
			root = root->right;
			continue;
		}
		Tree* parent = root->parent;
		while (parent && (parent->right==0 || parent->right==root)) {
			if (parent->right==0) {
				results.push_back(parent->data);
			}
			root = parent;
			parent = root->parent;
		}
		if (parent==0) {
			return results;
		}
		results.push_back(parent->data);
		root = parent->right;
	}
	return results;
}


///////////////////////

int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    int result;
    vector<int> ans;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i], NULL);
    }
    print_ascii_tree(root);

    ans = get_in_order_through_parent(root);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    cout << endl;
    
    ans.clear();
    ans = get_pre_order_through_parent(root);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    cout << endl;

    ans.clear();
    ans = get_post_order_through_parent(root);
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
    cout << endl;
}
